|
Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm, a method of multiplying two large integers. Given two large integers, ''a'' and ''b'', Toom–Cook splits up ''a'' and ''b'' into ''k'' smaller parts each of length ''l'', and performs operations on the parts. As ''k'' grows, one may combine many of the multiplication sub-operations, thus reducing the overall complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom-3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where ''k'' = 3. Toom-3 reduces 9 multiplications to 5, and runs in Θ(''n''log(5)/log(3)), about Θ(''n''1.465). In general, Toom-''k'' runs in Θ(''c''(''k'') ''ne''), where ''e'' = log(2''k'' − 1) / log(''k''), ''ne'' is the time spent on sub-multiplications, and ''c'' is the time spent on additions and multiplication by small constants.〔Knuth, p. 296〕 The Karatsuba algorithm is a special case of Toom–Cook, where the number is split into two smaller ones. It reduces 4 multiplications to 3 and so operates at Θ(''n''log(3)/log(2)), which is about Θ(''n''1.585). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(''n''2). Although the exponent ''e'' can be set arbitrarily close to 1 by increasing ''k'', the function ''c'' unfortunately grows very rapidly.〔〔Crandall & Pomerance, p. 474〕 The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005.〔Crandall & Pomerance, p. 536〕 An implementation described by Donald Knuth achieves the time complexity Θ(''n'' 2√(2 log ''n'') log ''n'').〔Knuth, p. 302〕 Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(''n'' log ''n'' log log ''n'')) becomes practical. Toom first described this algorithm in 1963, and Cook published an improved (asymptotically equivalent) algorithm in his PhD thesis in 1966.〔(Positive Results ), chapter III of Stephen A. Cook: ''On the Minimum Computation Time of Functions''.〕 ==Details== This section discusses exactly how to perform Toom-''k'' for any given value of ''k'', and is a simplification of a description of Toom–Cook polynomial multiplication described by Marco Bodrato.〔Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In ''WAIFI'07 proceedings'', volume 4547 of LNCS, pages 116–133. June 21–22, 2007. (author website )〕 The algorithm has five main steps: # Splitting # Evaluation # Pointwise multiplication # Interpolation # Recomposition In a typical large integer implementation, each integer is represented as a sequence of digits in positional notation, with the base or radix set to some (typically large) value ''b''; for this example we use ''b'' = 10000, so that each digit corresponds to a group of four decimal digits (in a computer implementation, ''b'' would typically be a power of 2 instead). Say the two integers being multiplied are: These are much smaller than would normally be processed with Toom–Cook (grade-school multiplication would be faster) but they will serve to illustrate the algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Toom–Cook multiplication」の詳細全文を読む スポンサード リンク
|